package bubblesort

// 冒泡排序的思想是：我要确保每一次遍历我拿到的数字是最大的或者最小的
// 因此，在每次比较的时候都会涉及到交换数组内数字的位置
// 注意一点就是，每次排序好的数字都放到的最后面
// 所以外层的循环是限制内存循环所对比的位置。
// 时间复杂度O(n^2) 空间复杂度O(1) 稳定排序
func BubbleSort(array []int) []int {
	for j := len(array) - 1; j >= 0; j-- {
		for i := 0; i < j; i++ {
			if array[i] > array[i+1] {
				array[i], array[i+1] = array[i+1], array[i]
			}
		}
	}

	return array
}

// 好奇怪哦，根据单元测试的结果来看，明明是优化过的算法，但是最终的效率却没有优化的要好
// 优化主要考虑两方面，一个是前一段有序，一个是后一段有序
// 前一段有序很简单，只要判断在一个最值的伦次中，没有交换，就证明我们假设的无序部分其实是有序的
// 而后一段是否有序也好判断，每次记录我们交换点的位置，当找到一个最值的时候，我们这个记录的交换点
// 就是最后一次交换的位置，也就是说之后的位置都是有序的了
func BubbleSortOptimization(array []int) []int {
	// 用来记录前一部分是否进行了交换，当没有交换的时候就是前一部分变的有序了，就不用排了
	var isSwap bool
	unorderedBounders := len(array) - 1
	var recordUnorderedBounders int = 0
	for i := 0; i < len(array); i++ {
		isSwap = false
		for j := 0; j < unorderedBounders; j++ {
			if array[j] > array[j+1] {
				array[j], array[j+1] = array[j+1], array[j]
				isSwap = true
				recordUnorderedBounders = j
			}
		}
		unorderedBounders = recordUnorderedBounders
		if !isSwap {
			break
		}
	}
	return array
}
